package org.aplombh.java.leetcode.all;

public class _33搜索旋转排序数组 {
    public static void main(String[] args) {
        System.out.println(new Solution33_1().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
    }
}

class Solution33_1 {
    public int search(int[] nums, int target) {
        return split(nums, 0, nums.length - 1, target);
    }

    public int split(int[] nums, int left, int right, int target) {

        if (left > right)
            return -1;

        int index;
        if (nums[left] < nums[right]) {
            index = binarySearch(nums, left, right, target);
        } else {
            int mid = (left + right) / 2;

            if (nums[mid] == target)
                return mid;

            index = split(nums, left, mid - 1, target);
            if (index == -1)
                index = split(nums, mid + 1, right, target);
        }

        if (index != -1 && nums[index] == target)
            return index;

        return -1;
    }

    public int binarySearch(int[] nums, int left, int right, int target) {

        if (left > right)
            return -1;

        int mid = (left + right) / 2;

        if (nums[mid] == target)
            return mid;
        if (target < nums[mid])
            return binarySearch(nums, left, mid - 1, target);
        return binarySearch(nums, mid + 1, right, target);
    }
}